package other;

import java.util.PriorityQueue;

/**
 * 题目：数据流中的中位数
 * <p>
 * 数据流中的中位数可以采用堆来处理
 * 一个堆存数据流的左边，一个堆存数据流的右边
 * @Author Gavin
 * @date 2022.08.06 16:13
 */
public class solution_8 {
    private PriorityQueue<Integer> maxLeft = new PriorityQueue<>(((o1, o2) -> o2 - o1));//大顶堆（顶部元素最大，也是最先出来的）
    private PriorityQueue<Integer> minRight = new PriorityQueue<>();//默认小顶堆
    int n = 0;

    /**
     * 两个堆形成了一个递增的序列，从大顶堆->小顶堆的数据是递增
     */
    public void insert(Integer num) {
        if ((n & 1) == 0) {
            maxLeft.add(num);
            minRight.add(maxLeft.poll());//这里可以看出来如果为奇数那么右边的元素要多一个，这样的操作方式是为了保证大小顶推之间的数据是平衡的
        } else {
            minRight.add(num);
            maxLeft.add(minRight.poll());
        }
        n++;
    }

    public Double solution() {
        if ((n & 1) == 0) {
            return (maxLeft.peek() + minRight.peek()) / 2.0;
        } else {
            return Double.valueOf(Integer.valueOf(minRight.peek()));
        }
    }
}
